/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    int a[210];
    int b[210];

public:
    ListNode* partition(ListNode* head, int x) {
        if(head == nullptr ) return nullptr;
        if(head->next == nullptr)return head;
        // 找到大于的 再找到小于的 加进去
        ListNode* p = head;
        int size1 = 1;
        int size2 = 1;
        int i = 0;
        int j = 0;
        while (p != nullptr) {
            if (p->val < x) {
                a[i] = p->val;
                i++;
                size1++;
            }
            if (p->val >= x) {
                b[j] = p->val;
                j++;
                size2++;
            }
            p = p->next;
        }
        p = head;
        i = 0;
        j = 0;
        for (i = 0; i < size1-1; ++i) {
            p->val = a[i];
            p = p->next;
        }
        for (int j = 0; j < size2-1; ++j) {
            if (p != nullptr) {
                p->val = b[j];
                p = p->next;
            }
        }
        return head;
    }
};
